Critère d'existence de solutions

Propriété

Soit \(a \in \mathbb{Z}\) , \(b \in \mathbb{Z}\) et \(c \in \mathbb{Z}\) non nuls. L'équation  \(ax+by=c\) possède des solutions si, et seulement si, \(\mathrm{PGCD}(a;b)\) divise \(c\) .

Démonstration

On note \(d=\mathrm{PGCD}(a;b)\) . Il existe des entiers \(a'\) et \(b'\) tels que \(a=a'd\) et \(b=b'd\) .

\([\Rightarrow]\) Supposons que l'équation \(ax+by=c\) admette une solution \((x_0;y_0)\) . On a alors  \(\begin{align*}ax_0+by_0=c& \ \ \Longleftrightarrow \ a'dx_0+b'dy_0=c\ \ \Longleftrightarrow \ d(a'x_0+b'y_0)=c\end{align*}\)  avec \(a'x_0+b'y_0 \in \mathbb{Z}\) , donc \(d\) divise \(c\) .

\([\Leftarrow]\) Supposons que \(d\) divise \(c\) . Il existe alors \(c' \in \mathbb{Z}\) tel que \(c=c'd\) . D'après le théorème de Bachet-Bézout, il existe \((u;v) \in \mathbb{Z}^2\) tel que \(au+bv=d\) . En multipliant cette égalité par \(c'\) , on obtient \(a(c'u)+b(c'v)=c'd=c\) .
Ainsi, le couple \((c'u;c'v)\) est une solution de l'équation \(ax+by=c\) .

Remarque

La propriété précédente assure que si \(\mathrm{PGCD}(a;b)\) ne divise pas \(c\) , alors l'équation \(ax+by=c\) n'a pas de solution dans \(\mathbb{Z}^2\) .